6961. Назначения

 

Когда штаб Звездного Флота получил запрос на исследовательскую экспедиции, стал вопрос какой из кораблей отправить из тех, которые сейчас находятся на стоянке в доке. Способность совершить кораблем экспедицию было решено определить на основе количества топлива, хранящегося на судне в настоящее время, а также времени прибытия корабля в точку назначения.

   Учитывая текущий возраст и качество обслуживания, каждый корабль движется с разной максимальной скоростью и имеет разную скорость потребления топлива. Каждое судно достигает максимальной скорости мгновенно.

 

Вход. Первая строка содержит количество тестов t (1 ≤ t ≤ 50). Каждый тест начинается со строки, содержащей два целых числа n и d, где n (1 ≤ n ≤ 100) – количество кораблей в доке, а d (1 ≤ d ≤ 106) – расстояние в световых годах до места экспедиции. Каждая из следующих n строк содержит три целых числа vi, fi и ci, где vi (1 ≤ vi ≤ 1000) – максимальная скорость корабля i в световых годах в час, fi (1 ≤ fi ≤ 1000) – масса топлива на корабле i в килограммах, и ci (1 ≤ ci ≤ 1000) – потребление топлива кораблем i в килограммах в час.

 

Выход. Для каждого теста вывести в отдельной строке количество кораблей, способных достичь места экспедиции. Будьте аккуратны с целочисленным делением!

 

Пример входа

Пример выхода

2

3 100

52 75 10

88 13 44

56 9 5

2 920368

950 950 1

943 976 1

2

1

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

i-ый корабль обладает запасом топлива, достаточного для движения fi / ci часов. Обладая скоростью vi, он способен преодолеть расстояние fi / ci * vi. Если оно меньше d, то i-ый корабль до места экспедиции не долетит.

 

Реализация алгоритма

Читаем входные данные. В переменной res для каждого теста подсчитываем количество кораблей, способных достичь места экспедиции.

 

scanf("%d",&tests);

while(tests--)

{

  res = 0;

  scanf("%d %d",&n,&d);

  for(i = 0; i < n; i++)

  {

    scanf("%d %d %d",&v,&f,&c);

 

Для очередного корабля проверяем, долетит ли он до места экспедиции.

 

    if (v * f >= d * c) res++;

  }

 

Выводим искомое количество кораблей.

 

  printf("%d\n",res);

}